Customers of a computing resource service provider may reduce expenses and overhead by using remote program execution and remote data storage services provided by the computing resource service provider. Customer applications may be distributed over multiple virtual machine instances and computing systems. In addition, these computing systems may include various block-level storage devices. In distributed computing environments, however, scalability, availability, durability, and performance are complex problems to solve, especially as the number of devices involved increases. Moreover, the many distributed computer systems involve computing resources that may occasionally fail and/or require repair. Adding to the complexity are differences in devices, such as different disk drives and, generally, differences that introduce additional factors to be taken into account when managing systems. As a result, maintaining scalability, availability, durability, and performance in distributed computing environments with heterogeneous computing resources that may occasionally fail and/or require repair is difficult and complex. In addition, this difficulty and complexity increases with the size of these distributed computing resource environments.